import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 力扣130. 被围绕的区域
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int n = board.length;
        int m = board[0].length;
        boolean[][] temp = new boolean[n][m];
        for(int i=0;i<n;i++){ // 列
            if(board[i][0] == 'O'&&!temp[i][0]){
                dfs(board,temp,i,0);
            }
            if(board[i][m-1] == 'O'&&!temp[i][m-1]){
                dfs(board,temp,i,m-1);
            }
        }
        for(int i=0;i<m;i++){ // 行
            if(board[0][i] == 'O'&&!temp[0][i]){
                dfs(board,temp,0,i);
            }
            if(board[n-1][i] == 'O'&&!temp[n-1][i]){
                dfs(board,temp,n-1,i);
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!temp[i][j] && board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void dfs(char[][] board, boolean[][] temp, int x, int y){
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length
                || board[x][y] == 'X' || temp[x][y]) {
            return;
        }
        temp[x][y] = true;
        dfs(board,temp,x-1,y); // 上
        dfs(board,temp,x+1,y); // 下
        dfs(board,temp,x,y-1); // 左
        dfs(board,temp,x,y+1); // 右
    }
}



// 力扣133. 克隆图
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}


class Solution1 {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> visited = new HashMap<>();
        return dfs(node, visited);
    }

    private Node dfs(Node node, Map<Node, Node> visited) {
        if (visited.containsKey(node)) { // 如果已经放入了node, cloneNode，那么就返回这个cloneNode
            return visited.get(node);
        }
        // 没有放入的话，那么就创建克隆节点，并放入
        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);
        for (Node neighbor : node.neighbors) { // 遍历题目给的node的neighbors
            cloneNode.neighbors.add(dfs(neighbor, visited));
        }
        return cloneNode;
    }
}